In many types of communication, there is a need to protect messages from tampering and unauthorized access. Encryption has long been used for such purposes. In advanced applications of encryption techniques, encryption keys are used not only to provide security for the encrypted messages, but also to protect the integrity of the messages. For example, a digital signature may be appended to a message prior to transmission, and a second version of the digital signature computed from the received message by the receiving party. If the two versions of the digital signature disagree, the receiving party will know that the integrity of the message was compromised by tampering.
To assure the integrity of a message, it is desirable to send the message, together with the appended digital signature, under the protection of a cipher that is non-malleable. The property of non-malleability assures that if even one bit of the encrypted message is changed as the result, e.g., of a malicious attack, the effects of the change will be distributed throughout the message upon decryption. Therefore, in particular, there will be a high probability that the digital signature is affected, and will fail to agree with the version locally computed by the receiving party.
One type of cipher used for encryption of messages is referred to as a block cipher. A block cipher takes blocks of binary data of fixed length as input strings, and produces blocks of binary data of fixed length as output strings. For example, Advanced Encryption Standard (AES) is a well-known block cipher that typically has input and output blocks of 128 bits.
One way to apply a block cipher such as AES is by Electronic Codebook (ECB) encryption. In ECB encryption, the message is divided into blocks of appropriate input length for the block cipher, and each block, in turn, is independently encrypted using the block cipher.
One weakness of ECB encryption is that it is susceptible to replay attacks. That is, an attacker may be looking for a recurrent string within the transmitted message. In ECB encryption, the recurrence of a plaintext string may lead to recurrence of the same encrypted string. In such a case, the recurrence may be recognized by the attacker.
Various attempts have been made to make encryption methods more robust against tampering, replay attacks, and other kinds of attack. One example of a more robust approach is described in U.S. patent Ser. No. 11/261,399, filed on Oct. 28, 2005 by S. Patel et al. under the title, “Air-Interface Application Layer Security For Wireless Networks,” and commonly assigned herewith. In that approach, a block cipher, for example, is used to generate a pair of pseudorandom strings A and B. The block X of plaintext is encrypted by forming the expression AX+B, where A and X are combined using polynomial multiplication. The combined use of the strings A and B provides non-malleability as well as robustness against reply attacks.
Although useful, such a polynomial encryption method is relatively costly because the multiplication operation for encryption and more so its inverse for decryption are computationally intense.
Hence, there remains a need for robust encryption methods that are economical in their use of computational resources.